#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

class CBTInserter {
  public:
    CBTInserter(BinaryTreeNode* root) : root_(root) {
      node_deque.push_back(root);
      while (node_deque.front()->left && node_deque.front()->right) {
        auto node = node_deque.front();
        node_deque.pop_front();
        node_deque.push_back(node->left);
        node_deque.push_back(node->right);
      }
    };

    BinaryTreeNode* insert(int v) {
      BinaryTreeNode* new_node = new BinaryTreeNode();
      new_node->value = v;
      auto parent_node = node_deque.front();
      if (!parent_node->left) {
        parent_node->left = new_node;
      } else {
        parent_node->right = new_node;
        node_deque.pop_front();
        node_deque.push_back(parent_node->left);
        node_deque.push_back(parent_node->right);
      }
      return parent_node;
    }

    BinaryTreeNode* get_root() {
      return root_;
    }

  private:
    deque<BinaryTreeNode*> node_deque;
    BinaryTreeNode* root_;
};

int main() {
  vector<int> vec = {1};
  BinaryTreeNode* root = CreateBinaryTree(vec);

  CBTInserter cbt(root);
  auto ret = cbt.insert(2);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(3);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(4);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(5);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(6);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(7);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(8);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(9);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(10);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(11);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  ret = cbt.insert(12);
  cout << "parent node: " << ret->value << endl;
  PrintBinaryTree(root);

  return 0;
}
